package Top200;

/**
 * @author zhangmin
 * @create 2022-02-19 10:28
 * KMP
 * 对文本串上的指针i从不回退，根据对匹配串的建模，对任何文本串相同的匹配串都会使用相同的模型--dp[][]记录匹配串的状态
 *
 * 通过相同前后缀来找到下一个位置next
 */
public class strStr28 {
    //h为文本串，nee为匹配串
    public int strStr(String haystack, String needle) {
        if (needle.length()==0) return 0;
        int n=haystack.length(),m=needle.length();

        haystack=" "+haystack;
        needle=" "+needle;
        char[] hc = haystack.toCharArray();
        char[] nc = needle.toCharArray();

        //next数组表示第i个位置不匹配时下一状态跳转位置
        int[] next=new int[m+1];
        //开始构造next数组，i从2开始，1位置默认为0，j从0开始
        for (int i = 2,j=0; i < m+1; i++) {
            // 匹配不成功的话，j = next(j)
            while (j>0&&nc[i]!=nc[j+1]) j=next[j];
            // 匹配成功的话，先让 j++
            if (nc[i]==nc[j+1]) j++;
            // 更新 next[i]，结束本次循环，i++
            next[i]=j;
        }
        //匹配过程,i=1,j=0开始,i在文本串上移动，j在匹配串上移动
        for (int i = 1,j=0; i < n+1; i++) {
            // 匹配不成功 j = next(j)
            while (j>0&&hc[i]!=nc[j+1]) j=next[j];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (hc[i]==nc[j+1]) j++;
            //全部匹配成功
            if (j==m){
                return i-m;
            }
        }
        return -1;
    }
}
